package dfs_bfs.leetcode_46;

import java.util.ArrayList;
import java.util.List;

public class BackTrace {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0){
            return res;
        }
        List<Integer> path = new ArrayList<>();
        boolean[] flag = new boolean[nums.length];
        dfs(nums, 0, res, path, flag);
        return res;
    }

    private void dfs(int[] nums, int depth, List<List<Integer>> res, List<Integer> path, boolean[] used) {
        if(depth == nums.length){
            /*
                Java 中的参数传递为值传递，由于 path 是引用类型，传递的参数是变量的地址
                在递归过程在 都使用同一个 path 指向的都是同一个内存地址
                因此在回溯的过程中，所有的元素都会从 path 中删除。

                所以这里保存一份 path 的拷贝
                错误写法：
                     res.add(path);
             */
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]){
                // 将当前元素保存到路径集合中，并设置为 true 表示该元素已经被使用
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, depth + 1, res, path, used);
                // 回溯，撤销该元素已经被选择的状态，保证后面的还能选择到该元素
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
